package com.cjm.algorithm.leetcode.listnode;

import com.cjm.algorithm.ListNode;

/**
 * {link https://leetcode-cn.com/problems/insertion-sort-list/}
 */
public class Ti147 {
    public static ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        // 虚拟头节点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        // 第一个默认是已经排好序的, 第二个开始所以cur = head.next
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                // 如果当前位置的值, 是大于前一个元素的, 那么说明这个元素的位置现在是正确的
                lastSorted = lastSorted.next;
            } else {
                // 前一个元素是虚拟节点
                ListNode prev = dummyHead;
                // 从第一个节点, 又开始去扫描, 直到这个值小于之前排序好的节点中的某个值
                while (prev.next.val <= curr.val) {
                    // 一直往后移动
                    prev = prev.next;
                }
                // ****************************
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
                // ****************************
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }

    public static ListNode insertionSortList1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode lastSorted = head;
        ListNode cur = head.next;

        while (cur != null) {
            if (lastSorted.val <= cur.val) {
                lastSorted.next = cur;
            } else {
                ListNode pre = dummyNode;
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }

                lastSorted.next = cur.next;
                cur.next = lastSorted;
                pre.next = cur;
            }
            cur = lastSorted.next;
        }

        return dummyNode.next;

    }
}
